using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Linq;
using System.Linq.Dynamic;
using YTS.Tools;

namespace Test.ConsoleProgram.Algorithm.Solution
{
    [TestDescription("算法: 0070. 爬楼梯")]
    public class No0070_ClimbStairs : AbsBaseTestItem
    {
        public override void OnTest()
        {
            Assert.TestExe(ClimbStairs, 1, 1);
            Assert.TestExe(ClimbStairs, 2, 2);
            Assert.TestExe(ClimbStairs, 3, 3);
            Assert.TestExe(ClimbStairs, 4, 5);
            Assert.TestExe(ClimbStairs, 5, 8);
            Assert.TestExe(ClimbStairs, 6, 13);
            Assert.TestExe(ClimbStairs, 7, 21);
            Assert.TestExe(ClimbStairs, 8, 34);
            Assert.TestExe(ClimbStairs, 9, 55);
            Assert.TestExe(ClimbStairs, 10, 89);
            Assert.TestExe(ClimbStairs, 11, 144);
            Assert.TestExe(ClimbStairs, 12, 233);
            Assert.TestExe(ClimbStairs, 13, 377);
            Assert.TestExe(ClimbStairs, 14, 610);
            Assert.TestExe(ClimbStairs, 15, 987);
            Assert.TestExe(ClimbStairs, 16, 1597);
            Assert.TestExe(ClimbStairs, 17, 2584);
            Assert.TestExe(ClimbStairs, 18, 4181);
            Assert.TestExe(ClimbStairs, 19, 6765);

            Assert.TestExe(ClimbStairs2, 1, 1);
            Assert.TestExe(ClimbStairs2, 2, 2);
            Assert.TestExe(ClimbStairs2, 3, 3);
            Assert.TestExe(ClimbStairs2, 4, 5);
            Assert.TestExe(ClimbStairs2, 5, 8);
            Assert.TestExe(ClimbStairs2, 6, 13);
            Assert.TestExe(ClimbStairs2, 7, 21);
            Assert.TestExe(ClimbStairs2, 8, 34);
            Assert.TestExe(ClimbStairs2, 9, 55);
            Assert.TestExe(ClimbStairs2, 10, 89);
            Assert.TestExe(ClimbStairs2, 11, 144);
            Assert.TestExe(ClimbStairs2, 12, 233);
            Assert.TestExe(ClimbStairs2, 13, 377);
            Assert.TestExe(ClimbStairs2, 14, 610);
            Assert.TestExe(ClimbStairs2, 15, 987);
            Assert.TestExe(ClimbStairs2, 16, 1597);
            Assert.TestExe(ClimbStairs2, 17, 2584);
            Assert.TestExe(ClimbStairs2, 18, 4181);
            Assert.TestExe(ClimbStairs2, 19, 6765);
        }

        public int ClimbStairs(int n)
        {
            int p = 0, q = 0, r = 1;
            for (int i = 1; i <= n; i++)
            {
                p = q;
                q = r;
                r = p + q;
            }
            return r;
        }

        public int ClimbStairs2(int n)
        {
            double sqrt5 = Math.Sqrt(5);
            double fibn = Math.Pow((1 + sqrt5) / 2, n + 1) - Math.Pow((1 - sqrt5) / 2, n + 1);
            return (int)(fibn / sqrt5);
        }
    }
}
